#include <algorithm>
#include <functional>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
// 排序 时间复杂度 O(NlogN)
vector<int> topKFrequent_(vector<int> &nums, int k) {
  // 1.统计频率
  unordered_map<int, int> counter;
  for (int i : nums) {
    counter[i]++;
  }
  vector<pair<int, int>> v;
  for (auto it = counter.begin(); it != counter.end(); it++) {
    v.push_back({it->first, it->second});
  }
  // 2.排序
  auto comp = [](pair<int, int> &x, pair<int, int> &y) {
    return x.second > y.second;
  };
  sort_heap(v.begin(), v.end(), comp);
  vector<int> res;
  for (int i = 0; i < k; i++) {
    res.push_back(v[i].first);
  }
  return res;
}

// partition 算法
int partition(vector<pair<int, int>> &nums, int left, int right) {
  int pivotIndex = right;
  int pivot = nums[right].second;
  int i = left;
  for (int j = left; j < right; j++) {
    if (nums[j].second < pivot) {
      swap(nums[i++], nums[j]);
    }
  }
  swap(nums[i], nums[right]);
  return i;
}

vector<int> topKFrequent(vector<int> &nums, int k) {
  // 1.统计频率
  unordered_map<int, int> counter;
  for (int i : nums) {
    counter[i]++;
  }
  vector<pair<int, int>> v;
  for (auto it = counter.begin(); it != counter.end(); it++) {
    v.push_back({it->first, it->second});
  }
  // 2.排序
  int pos = v.size() - k;
  int left = 0;
  int right = v.size() - 1;
  while (left < right) {
    int p = partition(v, left, right);
    if (p == pos) {
      break;
    }
    if (p < pos) {
      left = p + 1;
    }
    if (p > pos) {
      right = p - 1;
    }
  }
  vector<int> res;
  for (int i = pos; i < v.size(); i++) {
    res.push_back(v[i].first);
  }
  return res;
}